#include "BinaryMinHeap.h"
#include <iostream>

int BinaryMinHeap::getLeftChildIndex(int nodeIndex) 
{
	return 2 * nodeIndex + 1;
}
int BinaryMinHeap::getRightChildIndex(int nodeIndex) 
{
	return 2 * nodeIndex + 2;
}
int BinaryMinHeap::getParentIndex(int nodeIndex) 
{
	return (nodeIndex - 1) / 2;
}

BinaryMinHeap::BinaryMinHeap() 
{
	data = new Event*[capacity];
	heapSize = 0;
	arraySize = capacity;
}    

Event* BinaryMinHeap::getMinimum() 
{
	if (isEmpty())
	{
		std::cout << "Heap is empty\n";
		throw "Heap is empty";
	}
	else
		return data[0];
}

bool BinaryMinHeap::isEmpty() {
	return (heapSize == 0);
}
BinaryMinHeap::~BinaryMinHeap() {
	delete[] data;
}

void BinaryMinHeap::siftUp(int nodeIndex) {
	int parentIndex;
	Event*  tmp;
	if (nodeIndex != 0) 
	{
		parentIndex = getParentIndex(nodeIndex);
		if (*data[parentIndex] > *data[nodeIndex]) {
			tmp = data[parentIndex];
			data[parentIndex] = data[nodeIndex];
			data[nodeIndex] = tmp;
			siftUp(parentIndex);
		}
	}
}

void BinaryMinHeap::addEvent(Event* value) {
	if (heapSize == arraySize)
	{
		Event** newData = new Event*[arraySize + capacity];
		for (int i = 0; i < arraySize; i++)
			newData[i] = data[i];
		delete [] data;
		data = newData;
		arraySize += capacity;
	}
	heapSize++;
	data[heapSize - 1] = value;
	siftUp(heapSize - 1);
	
}

void BinaryMinHeap::siftDown(int nodeIndex)
{
	int leftChildIndex, rightChildIndex, minIndex;
	Event* tmp;
	leftChildIndex = getLeftChildIndex(nodeIndex);
	rightChildIndex = getRightChildIndex(nodeIndex);
	if (rightChildIndex >= heapSize) 
	{
		if (leftChildIndex >= heapSize)
			return;
		else
			minIndex = leftChildIndex;
	} 
	else 
	{
		if (*data[leftChildIndex] <= *data[rightChildIndex])
			minIndex = leftChildIndex;
		else
			minIndex = rightChildIndex;
	}
	if (*data[nodeIndex] > *data[minIndex]) 
	{
		tmp = data[minIndex];
		data[minIndex] = data[nodeIndex];
		data[nodeIndex] = tmp;
		siftDown(minIndex);
	}
}

 

Event* BinaryMinHeap::pop() {
	if (isEmpty())
	{
		std::cout << "Heap is empty\n";
		throw "Heap is empty";
	}
	else 
	{
		Event* min = data[0];
		data[0] = data[heapSize - 1];
		heapSize--;
		if (heapSize > 0)
			siftDown(0);
		return min;
	}	
}